package offer_test_40;

//在数组中的两个数字如果前一个数字大于后一个数字，则这两个数字组成一个逆序对。
//输入一个数组，求出这个数组的逆序对的总数。例如在数组{7,5,6,4}中，一共存在5个逆序对，
//分别是（7,6）、（7、5），（7、4），（6、4），（5、4）。
public class sixteen_InversePairs {
	public static void main(String[] args) {
		int[] array = { 7, 5, 6, 4, 1 };
		InversePairs(array);
	}
	//采取归并排序，同时计算逆序数
	public static void InversePairs(int[] array) {
		System.out.println(sort(array, 0, array.length - 1));
	}

	public static int sort(int[] data, int left, int right) {
		if (left >= right) {
			return 0;
		}
		// 找出中间索引
		int center = (left + right) / 2;
		// 对左边数组进行递归
		int leftcount = sort(data, left, center);
		// 对右边数组进行递归
		int rightcount = sort(data, center + 1, right);
		// 合并
		int count = merge(data, left, center, right);
		return count + rightcount + leftcount;
	}

	/**
	 * 将两个数组进行归并，归并前面2个数组已有序，归并后依然有序
	 * 
	 * @param array
	 * @param begin
	 *            左数组的第一个元素的索引
	 * @param center
	 *            左数组的最后一个元素的索引，center+1是右数组第一个元素的索引
	 * @param end
	 *            右数组最后一个元素的索引
	 */
	public static int merge(int[] array, int begin, int center, int end) {
		int[] temp = new int[array.length];
		int leftbegin = begin;
		int leftend = center;
		int rightbegin = center + 1;
		int rightend = end;
		int tempbegin = end;
		int count = 0;
		while (leftbegin <= leftend && rightbegin <= rightend) {
			if (array[leftend] <= array[rightend]) {
				temp[tempbegin] = array[rightend];
				tempbegin--;
				rightend--;
			} else {
				temp[tempbegin] = array[leftend];
				tempbegin--;
				leftend--;
				count = count + rightend - rightbegin + 1;
			}
		}
		while (rightbegin <= rightend) {
			temp[tempbegin] = array[rightend];
			tempbegin--;
			rightend--;
		}
		while (leftbegin <= leftend) {
			temp[tempbegin] = array[leftend];
			tempbegin--;
			leftend--;
		}
		while (begin <= end) {
			array[end] = temp[end];
			end--;
		}
		return count;
	}
}
